package com.mlh.dp.old;

// 题目：
// 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
// 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
// 举例：输入：s="bbbab"
// 输出：4
// 解释：一个可能的最长回文子序列为"bbbb" 。

public class LongestPalindromeSubseq {

    //思路：dp[i][j]表示的s的i-j的字符串的最大回文子序列
    //i和j 有3种情况
    //j-i=0 此时dp[i][j]=1
    //j-i=1 此时dp[i][j]取决于i和j是否相同  相同为2 不同则为1
    //j-i>1 此时dp[i][j]取决于i和j是否相同  相同为2+dp[i+1][j-1]  不同则Math.max(dp[i + 1][j], dp[i][j - 1]);
    //递归版本
    public static int method1(String s ,int head,int tail){
        if(head>tail){
            return 0;
        }
        if(s.charAt(head)==s.charAt(tail)){
           if(head==tail){
               return 1;
           }else{
               if(head+1==tail){
                   return 2;
               }
               return 2+method1(s,head+1,tail-1);
           }
        }
        return Math.max(method1(s,head+1,tail),method1(s,head,tail-1));
    }

    //记忆搜索
    public static int method2(String s,int head,int tail,int[][]dp){
        if(head>tail){
            return 0;
        }
        if(dp[head][tail]!=-1){
            return dp[head][tail];
        }
        if(s.charAt(head)==s.charAt(tail)){
            if(head==tail){
                dp[head][tail]=1;
                return dp[head][tail];
            }else{
                if(head+1==tail){
                    dp[head][tail]=2;
                    return dp[head][tail];
                }
                dp[head][tail]=2+method1(s,head+1,tail-1);
                return dp[head][tail];
            }
        }
        dp[head][tail]=Math.max(method1(s,head+1,tail),method1(s,head,tail-1));
        return dp[head][tail];
    }

    //严格表依赖
    public static int method3(String s) {
        int len=s.length();
        int[][] dp = new int[len][len];
        for (int i = len-1; i>=0; --i) {
            for (int j =i; j<len; ++j) {
                if(i==j){
                    dp[i][j] = 1;
                    continue;
                }
                if (s.charAt(i) == s.charAt(j)) {
                    if (i + 1 == j) {
                        dp[i][j] = 2;
                    } else{
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    }
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][len-1];
    }


    //method4是method3的优化  将字符串转成字符数组处理  会比String 的 charAt()方法快很多
    //本质也就是空间换时间
    public static int method4(String s) {
        int len=s.length();
        char[]sChar=s.toCharArray();
        int[][] dp = new int[len][len];
        for (int i = len-1; i>=0; --i) {
            dp[i][i]=1;
            for (int j =i+1; j<len; ++j) {
                if (sChar[i] == sChar[j]) {
                    if (i + 1 == j) {
                        dp[i][j] = 2;
                    } else{
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    }
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][len-1];
    }
}
